package 八大排序;

/**
 * 快速排序：要求时间最快时。
 * @author 刘学松
 * @date 2021/2/25 19:12
 */
public class 快速排序 {
    public static void main(String[] args) {
        quickSort(ArrayUtils.array, 0, ArrayUtils.array.length-1);
        ArrayUtils.printArray(ArrayUtils.array);
    }

    public static void quickSort(int[] a, int start, int end) {
        if (start < end) {
            int left = start, right = end;
            // 定义第一个元素为基数
            int base = a[start];
            while (left < right) {
                while (left<right && a[right] >= base) {
                    right--;
                }
                if (left < right) {
                    a[left++] = a[right];
                }

                while (left < right && a[left] <= base) {
                    left++;
                }
                if (left < right) {
                    a[right--] = a[left];
                }
            }
            a[left] = base;
            quickSort(a, start, left - 1);
            quickSort(a, right + 1, end);
        }
    }
}
